import java.util.Random;

public class FindKthLargest {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int targetIndex = len - k;
        int left = 0, right = len - 1;
        while (true) {
            int pivot = findPartitionIndex(nums, left, right);
            if (pivot == targetIndex) return nums[targetIndex];
            else if (targetIndex < pivot) right = pivot - 1;
            else left = pivot + 1;
        }
    }

    private int findPartitionIndex(int[] nums, int left, int right) {
        int randIndex = left + random.nextInt(right - left + 1);
        swap(nums, left, randIndex);
        int i = left + 1, j = right;
        int pivot = nums[left];
        while (true) {
            while (i <= j && nums[i] < pivot) i++;
            while (i <= j && nums[j] > pivot) j--;
            if (i >= j) break;
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }

    public static void main(String[] args) {
        FindKthLargest f = new FindKthLargest();
        int[] nums = {3,2,1,5,6,4};
        System.out.println(f.findKthLargest(nums, 2));
    }
}
